#include "PageCache.h"

PageCache PageCache::_pagechche;

//从页缓存里得到一个k页的span
Span* PageCache::newSpan(size_t k)
{
	assert(k > 0 && k < NPAGES);
	// 先检查第k个页下是否有空间，有就直接返回
	if (!_spanLists[k].Empty())
	{
		return _spanLists->Pop();
		//std::cout << "PageCache.cpp 13 " << "if" << std::endl;
	}
	// 走到这里说明第k个页下面没有空间，从k+1开始遍历，看后面有没有可以页里有用的span
	int j = 0;
	for (int i = k + 1; i < NPAGES; i++)
	{
		if (!_spanLists[i].Empty())
		{
			//std::cout << j++ << std::endl;
			Span* nspan = _spanLists[i].Pop();
			Span* kspan = new Span;

			// 在nspan的头部切一个k页下来
			kspan->PageId = nspan->PageId;
			kspan->n += k;

			// 修改nspan的剩余的实际页数和他指向的页id
			nspan->PageId += k;
			nspan->n -= k;

			// 将刚才分配给kspan的空间插入到_spanLists中
			_spanLists[nspan->n].PushFront(nspan);
			//std::cout << "PageCache.cpp 35 " << " while中的if" << std::endl;

			//将页的起始位置都映射在哈希表内，方便后面合并时可以方便的找到需要合并的span
			_idSpanMap[nspan->PageId] = nspan;
			_idSpanMap[nspan->PageId + nspan->n - 1] = nspan;

			// 建立id和span的映射，方便central cache回收小块内存时，查找对应的span
			for (PAGEID i = 0; i < kspan->n; i++)
			{
				// 将一个桶内的span管理的每一页都在哈希表内做一个映射，方便centralcache回收时知道哪些页的使用状态
				_idSpanMap[kspan->PageId + i] = kspan;
			}
			return kspan;
		}
	}

	// 走到这里说明PageCache也没有空间可用，需要向堆申请一个128页的span
	Span* bigSpan = new Span;
	void* ptr = SystemAlloc(NPAGES - 1);// NPAGES -1= (2^7) 128,最后返回2^20字节的空间
	// 将申请的空间转换为页id
	bigSpan->PageId = (PAGEID)ptr >> PAGE_SHIFT;// 右移13位就可以得到[1,128]的页号
	bigSpan->n = NPAGES - 1;// Span里管理了128个页
	_spanLists[bigSpan->n].PushFront(bigSpan);// 插入到指定的页的头部
	//std::cout << "递归执行中" << (wk += 1) << std::endl;
	return newSpan(k);
}
// 获取从对象到span的映射
Span* PageCache::MapObjectToSpan(void* obj)
{
	PAGEID id = ((PAGEID)obj >> PAGE_SHIFT);
	auto ret = _idSpanMap.find(id);
	if (ret == _idSpanMap.end())
	{
		assert(false);
		return nullptr;
	}
	return ret->second;
}

// 释放空闲span回到Pagecache，并合并相邻的span
void PageCache::ReleaseSpanToPageCache(Span* span)
{
	//对span前后的页进行合并，缓解内碎片问题
	//内碎片：已经分配出去的空间，但是由于对齐等原因会比实际需要的多出来一点，且这部分无法使用
	//外碎片：没有分配出去的空间，空间总和可以满足实际需要的空间，但是这些空间不连续，无法分配
	while (1)
	{
		// 先对当前页的前面进行查找是否有可以合并的页
		PAGEID previd = span->PageId - 1;
		auto ret = _idSpanMap.find(previd);

		//前面不存在页，就不合并了
		if (ret == _idSpanMap.end())break;

		// 如果这个页正在使用，也不能合并
		Span* newspan = ret->second;
		if (newspan->_isUse)break;

		// 如果合并出超过128页的span无法管理，也不合并了
		if (newspan->n + span->n > NPAGES - 1)break;

		span->PageId += newspan->PageId;
		span->n += newspan->n;

		//合并页成功后删除这部分
		_spanLists[newspan->n].Erase(newspan);

		delete newspan;
	}


	// 合并当前页之后的页
	while (1)
	{
		// 先对当前页的前面进行查找是否有可以合并的页
		PAGEID nextid = span->PageId + span->n;
		auto ret = _idSpanMap.find(nextid);

		//前面不存在页，就不合并了
		if (ret == _idSpanMap.end())break;

		// 如果这个页正在使用，也不能合并
		Span* newspan = ret->second;
		if (newspan->_isUse)break;

		// 如果合并出超过128页的span无法管理，也不合并了
		if (newspan->n + span->n > NPAGES - 1)break;

		span->n += newspan->n;

		//合并页成功后删除这部分
		_spanLists[newspan->n].Erase(newspan);

		delete newspan;
	}

	// 将合并后的span重新挂回PageCache,然后对这部分在哈希表内做映射,保证每一页都能在哈希表中找到对于的span
	_spanLists[span->n].PushFront(span);
	span->_isUse = false;
	_idSpanMap[span->PageId] = span;
	_idSpanMap[span->PageId + span->n - 1] = span;

}